import java.util.*;

public class 二叉树的层序遍历 {
    //https://leetcode.cn/problems/binary-tree-level-order-traversal/
    //可以直接用bfs, 这里我直接采用一个手写队列, 也可以用Queue来

    //手写队列, 用左右指针来维护队列
    public static int HMAX = 2100;
    public static TreeNode[] queue = new TreeNode[HMAX];
    public static int l;
    public static int r;
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        //添加根节点
        if(root == null){
            return ret;
        }
        l = r = 0;
        queue[r++] = root;
        while(l < r){
            //每次弹出的元素, 创建这层的表
            int size = r - l;
            List<Integer> list = new ArrayList<>();

            while(size -- != 0){
                TreeNode cur = queue[l++];
                list.add(cur.val);
                if(cur.left != null){
                    queue[r++] = cur.left;
                }
                if(cur.right != null){
                    queue[r++] = cur.right;
                }
            }
            ret.add(list);
        }
        return ret;
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}